﻿using System;
using System.Collections.Generic;

namespace HashSearch
{
	/// <summary>
	/// 哈希查找时间复杂度O(1)。
	/// </summary>
	public class Program
	{
		//"除法求余法"
		static int hashLength = 13;
		//原数据
		static List<int> list = new List<int>() { 13, 29, 27, 28, 26, 30, 38 };
		//哈希表长度
		static int[] hash = new int[hashLength];

		static void Main(string[] args)
		{
			//创建哈希表
			for (int i = 0; i < list.Count; i++)
			{
				InsertHash(hash,hashLength,list[i]);
			}
			Console.WriteLine("hash表数据："+string.Join(",",hash));
			while (true)
			{
				Console.WriteLine("\n请输入要查找的数字:");
				int result = int.Parse(Console.ReadLine());
				var index = SearchHash(hash, hashLength, result);
				if (index != -1)
                     Console.WriteLine("数字" + result + "在索引的位置是:" + index);
                else
                     Console.WriteLine("呜呜，" + result + " 在hash中没有找到！");
				Console.ReadLine();
			}
		}

		public static int  SearchHash(int[] hash,int hashLength,int key)
		{
			//哈希函数
			int hashAddress = key % hashLength;
			//指定hashAddress对应值存在但不是关键值,则用开放寻址方法解决
			while (hash[hashAddress] != 0 && hash[hashAddress]!=key)
			{
				hashAddress = (++hashAddress) % hashLength;
			}
			//查找到了开放单元，表示查找失败
			if (hash[hashAddress] == 0)
				return -1;
			return hashAddress;
		}

		/// <summary>
		/// 数据插入Hash表
		/// </summary>
		/// <param name="hash"></param>
		/// <param name="hashLength"></param>
		/// <param name="data"></param>
		public static void InsertHash(int[] hash,int hashLength,int data)
		{
			//哈希函数
			int hashAddress = data % hashLength;
			//如果key存在，则说明已经被别人占用，此时必须解决冲突
			while (hash[hashAddress]!=0)
			{
				hashAddress = (++hashAddress)%hashLength;
			}
			//将data存入字典中
			hash[hashAddress] = data;
		}
	}
}
